package leetcode

//https://leetcode.com/problems/implement-strstr/
fun main(args: Array<String>) {

    println(strStr(
            "mississippi",
            "issipi"))
}

fun strStr(haystack: String, needle: String): Int {

    if (needle.isEmpty()) return 0
    if (needle.length > haystack.length) return -1

    var i = 0
    var j = 0
    var prev = -1

    while (j < needle.length && i < haystack.length) {
        if (needle[j] != haystack[i]) {
            j = -1
            //如果匹配失败了，那么在存在头部匹配的情况下应该回溯到匹配的后一位重新开始
            if (prev != -1) i = prev
            prev = -1
        } else {
            //记录上一次第一个匹配的位置
            if (prev == -1)
                prev = i
        }
        i++
        j++

    }

    //容易忽略的情况：在匹配到末尾的时候prev记录了值，但是haystack已经结束，退出循环，导致prev有值，但是并没有匹配完
    if (j != needle.length) prev = -1

    return prev
}